package hard

func FindIntegers(n int) int {
	dp := make([]int, 31)
	dp[0], dp[1] = 1, 1
	for i := 2; i < 31; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	pre, res := 0, 0
	for i := 29; i >= 0; i-- {
		val := 1 << i
		if (n & val) != 0 {
			res += dp[i+1]
			if pre == 1 {
				break
			}
			pre = 1
		} else {
			pre = 0
		}
		if i == 0 {
			res++
		}
	}
	return res
}
